#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/29 16:34
# ===========================================
#       题目名称： 47. 全排列 II
#       题目地址： https://leetcode.cn/problems/permutations-ii/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
from typing import List


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res_dict = dict()  # 返回值字典 k 已排序的值 v 未排序的值
        cur_carry, size = 0, len(nums)  # 当前位数 列表大小
        while cur_carry < size:
            if res_dict:
                temp_res_dict = dict()
                for k, v in res_dict.items():
                    for i in range(len(v)):
                        temp_v = v.copy()
                        del temp_v[i]
                        temp_res_dict[k + (v[i],)] = temp_v
                res_dict = temp_res_dict
            else:
                for i in range(size):
                    temp_nums = nums.copy()
                    del temp_nums[i]
                    res_dict[(nums[i],)] = temp_nums
            # print("cur_carry = %s, res_dict = %s" % (cur_carry, res_dict))
            cur_carry += 1

        return [list(item) for item in res_dict.keys()]


if __name__ == '__main__':
    s = Solution()
    # [[1, 1, 2],[1, 2, 1],[2, 1, 1]]
    print(s.permuteUnique(nums=[1, 1, 2]))
    # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    print(s.permuteUnique(nums=[1, 2, 3]))
